package com.atfcm.link;

/**
 * @Author whaty
 * @create 2024/11/6 16:44
 */
public class t92反转链表2 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null || head.next == null || right -left == 0 ) return head;
        int index = 1;
        ListNode pre = null;
        ListNode cur = head;

        ListNode end = null;
        ListNode start = null;
        while (index <= right && cur != null) {
            if(index+1 == left){
                start = cur;
            }
            if(index == right){
                end = cur.next;
            }
            if(index >= left){
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }else {
                cur = cur.next == null ?cur : cur.next;
            }
            index++;
        }

        end = cur;
        cur = pre;
        if(start == null && end == null){
            return cur;
        }
        if(start == null && end != null){
            head.next = end;
            return cur;
        }
        if(start != null && end == null){
            start.next = cur;

            return head;
        }
        if(start != null && end != null){
            start.next.next = end;
            start.next = cur;
            return head;
        }
        return null;
    }


        // 解法2
       public ListNode reverseBetween2(ListNode head, int left, int right) {
        if(head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode leftPre = dummy;
        for (int i = 0; i < left-1; i++) {
            leftPre = leftPre.next;
        }

        ListNode rightCur = leftPre;
        for (int i = 0; i < right-left+1; i++) {
            rightCur= rightCur.next;
        }
        ListNode rightNext = rightCur.next;

        // 注意断开链表。使新链表有结尾
        rightCur.next = null;
        ListNode lp = leftPre.next;

        ListNode revep = rever(lp);
        leftPre.next = revep;
        lp.next = rightNext;
        return dummy.next;
    }

    public ListNode rever(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode p  = rever(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }


     static   class ListNode {
        public int val;
        public ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }
}
